package com.kevinkk.backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个 【无重复元素】 的整数数组 candidates 和一个目标整数 target ，
 * 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * candidates 中的 同一个 数字可以 【无限制重复被选取】 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 */

/**
 * 即使每个元素可以无限制的被重复选取，仍然需要 startIndex 来进行去重
 * 在 CombinationSumIII 中，每个元素只能选取 1 次，因此 之后递归时，startIndex = i+1
 * 在 CombinationSumII  中，每个元素只能选取 1 次, 但是集合中有重复的元素，因此不仅之后递归时，startIndex = i+1，而且还需要借助 used 数组进行去重
 * 在 CombinationSum    中，每个元素可以选择无数次，因此 之后递归时，startIndex = i， 表示之前的元素依旧可以被选择
 */

public class CombinationSum {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            backtracking(candidates, target, 0, 0);
            return res;
        }

        private void backtracking(int[] candidates, int target, int startIndex, int sum){
            if(sum >= target){
                if(sum == target) res.add(new ArrayList<>(path));
                return;
            }

            for(int i = startIndex; i < candidates.length; i++){
                path.add(candidates[i]);
                backtracking(candidates, target, i, sum+candidates[i]);
                path.remove(path.size()-1);
            }
        }
    }
}
